package 牛客网编程.剑指offer.重建二叉树;

/**
 * @author Veng Su 1344114844@qq.com
 * @date 2018/7/14 16:59
 */
/*
一、根据前序加中序遍历重建二叉树
构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。

二、根据中序加后序遍历重建二叉树
构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        if (pre.length == 1) {
            return root;
        }
        int root_val = root.val;
        int i;
        for (i = 0; i < in.length; i++) {
            if (in[i] == root_val) {
                break;
            }
        }
        if (i > 0) {
            int[] lef_pre = new int[i];
            int[] lef_in = new int[i];
            System.arraycopy(pre, 1, lef_pre, 0, i);
            System.arraycopy(in, 0, lef_in, 0, i);
            root.left = reConstructBinaryTree(lef_pre, lef_in);
        } else root.left = null;
        if (i < in.length - 1) {
            int[] rig_pre = new int[in.length - i - 1];
            int[] rig_in = new int[in.length - i - 1];
            System.arraycopy(pre, i + 1, rig_pre, 0, in.length - i - 1);
            System.arraycopy(in, i + 1, rig_in, 0, in.length - i - 1);
            root.right = reConstructBinaryTree(rig_pre, rig_in);
        } else root.right = null;
        return root;
    }
}